package main

import (
	"fmt"
	"math"
)

func main() {
	fmt.Println(rob([]int{2, 7, 9, 3, 1}))
}

func rob(nums []int) int {
	dp := make([]int, len(nums))
	if len(nums) == 0 {
		return 0
	}

	for k := range nums {
		if k == 0 {
			dp[k] = nums[0]
			continue
		}

		if k == 1 {
			dp[k] = int(math.Max(float64(nums[0]), float64(nums[1])))
			continue
		}

		dp[k] = int(math.Max(float64(dp[k-2])+float64(nums[k]), float64(dp[k-1])))

	}

	return dp[len(nums)-1]
}

// dp表示偷k个房间的最高金额
// 如果没有房间 dp[0] = 0
// 如果有一个房间 dp[1] = 1
// 如果偷第k个房间，则不能偷 k-1个房间 则 最大金额为:dp[k] =  dp[k-2] + nums[k]
// 如果不偷第k个房间 dp[k] = dp[k-1]
// 所以 dp[k] = max(dp[k-2]+nums[k],dp[k-1])
